#define _CRT_SECURE_NO_WARNINGS
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//class Solution {
//public:
//    void merge(ListNode* l1, ListNode* l2, ListNode* head)
//    {
//        if (l1 == nullptr)
//        {
//            head->next = l2;
//            return;
//        }
//        else if (l2 == nullptr)
//        {
//            head->next = l1;
//            return;
//        }
//
//        if (l1->val < l2->val)
//        {
//            head->next = l1;
//            l1 = l1->next;
//        }
//        else
//        {
//            head->next = l2;
//            l2 = l2->next;
//        }
//        merge(l1, l2, head->next);
//    }
//
//    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
//        ListNode* head = new ListNode;
//        merge(l1, l2, head);
//        return head->next;
//    }
//};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//class Solution {
//public:
//    ListNode* dfs(ListNode* l1, ListNode* l2)
//    {
//        if (l1 == nullptr)
//        {
//            return l2;
//        }
//        else if (l2 == nullptr)
//        {
//            return l1;
//        }
//
//        if (l1->val < l2->val)
//        {
//            l1->next = dfs(l1->next, l2);
//            return l1;
//        }
//        else
//        {
//            l2->next = dfs(l1, l2->next);
//            return l2;
//        }
//    }
//
//    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
//        return dfs(l1, l2);
//    }
//};